# !/usr/bin/python
# -*- coding: utf-8 -*-
'''
@File    :   15_binary_search.py
@Time    :   2021/04/02 16:05:48
@Author  :   Qingxiang Zhang
@Version :   1.0
@Contact :   344285081@qq.com
@Desc    :   二分查找
@Software:    Vscode
'''
'''
二分查找，先排序，之后将其二分法，将产生查找
递归实现与非递归实现
'''
'''
递归方式
'''
def binary_search1(aList,item):
    n =len(aList)
    if n > 0:
        mid = n // 2       
        if aList[mid] == item:
            return True
        elif item < aList[mid]:
            return binary_search1(aList[:mid],item)
        else:
            return binary_search1(aList[mid+1:],item)
    return False

def binary_search2(aList,item):
    n = len(aList)
    first = 0
    last = n-1
    while first <= last:
        mid = (first+last)//2
        if aList[mid] == item:
            return True
        elif item < aList[mid]:
            last = mid -1
        else:
            first = mid +1
    return False
    

if __name__=="__main__":
    ali=[2,4,6,8,9,13,57,99]
    print(binary_search1(ali,77))
    # print(search)
    print(binary_search2(ali,99))
    print(binary_search2(ali,77))

